// 题目描述
// 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。
// 小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。
// 小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

// 输入描述
// 第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。 
// 接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

// 输出描述
// 输出一个整数，代表小明从起点到终点所花费的最小时间。当从起始车站不能到达终点车站时，则输出 -1。

// 输入示例
// 7 9
// 1 2 1
// 1 3 4
// 2 3 2
// 2 4 5
// 3 4 2
// 4 5 3
// 2 6 4
// 5 7 4
// 6 7 9
// 输出示例
// 12

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 邻接矩阵适合边比较多的情况，因为循环的是节点，如果边比较多，邻接矩阵比较稠密。否则浪费空间，循环起来也浪费时间，此时较适合使用邻接表作为图（以点为维度）
// 因为都是找距离头结点和值最小的节点，所以把当前未访问的节点和距离头结点的距离和存储到queue队列，存储时，进行排序。然后依次对queue进行访问。（以边为维度）
// 时间复杂度：O(ElogE) E 为边的数量。访问边*排序
// 空间复杂度：O(N + E) N 为节点的数量
void async function () {
    line = await readline();
    let [n, m] = line.split(' ').map(Number),
        minDist = new Array(n + 1).fill(50000),
        visited = new Array(n + 1).fill(false),
        // 声明邻接表
        graph = new Array(n + 1).fill(0).map(() => new Array()),
        // 存储当前边和距离顶点的路径和，排序后取最小值
        queue = [],
        parent = new Array(n + 1).fill(1),
        start = 1;

    minDist[start] = 0;
    while (line = await readline()) {
        let [left, right, val] = line.split(' ').map(Number);
        // 初始化邻接表，不仅要放可访问的节点，还要放权值，否则还要再找一遍权值
        graph[left].push(new Edge(right, val))
    }

    // 初始化队列，当前开始节点，和距离当前点的距离0
    queue.push(new QueueNode(start, 0))

    while (queue.length > 0) {
        // 目前的访问节点，一直都是距离顶点的和最小的节点，排序，如果后续有相同节点大的路径和，将continue掉
        let nodeItem = queue.shift()
        if (visited[nodeItem.node]) continue
        visited[nodeItem.node] = true
        // 遍历当前节点的邻接点
        for (let item of graph[nodeItem.node]) {
            // 如果邻接点没有被访问过，且当前点+两边权值比邻接点的距离顶点的和要小，更新minDist
            if (visited[item.to] === false && minDist[nodeItem.node] + item.val < minDist[item.to]) {
                minDist[item.to] = minDist[nodeItem.node] + item.val
                // 放到queue队列中并排序
                queue.push(new QueueNode(item.to, minDist[item.to]))
                queue.sort((a, b) => a.pathSum - b.pathSum)
                // 更新距离顶点最近的距离的父节点
                parent[item.to] = nodeItem.node
            }
        }
    }

    console.log(minDist[n] === 50000 ? -1 : 12)
}()

// 邻接表中存储的结构，可访问的节点，和对应边的权值
class Edge {
    constructor(to, val) {
        this.to = to
        this.val = val
    }
}

// 队列中节点，存储当前访问过的节点和距离顶点最近的路径和
class QueueNode {
    constructor(node, pathSum) {
        this.node = node
        this.pathSum = pathSum
    }
}